1. Field of the Invention
The present invention relates to decoding of encoded and transmitted data in a communication system, and, more particularly, to maximum a priori (MAP) decoding algorithms.
2. Description of the Related Art
MAP algorithms are employed for processing a channel output signal applied to a receiver. MAP algorithms may be used for both detection (to reconstruct estimates for transmitted symbols) and decoding (to reconstruct user data). A MAP algorithm provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. A MAP algorithm forms a trellis corresponding to possible states (portion of received symbols or data in the sequence) for each received output channel sample per unit increment in time (e.g., clock cycle).
A trellis diagram may represent states, and transitions between states, of the Markov process spanning an interval of time. The number of bits that a state represents is equivalent to the memory of the Markov process. Thus, probabilities (sometimes of the form of log-likelihood ratio (LLR) values) are associated with each transition within the trellis, and probabilities are also associated with each decision for a sample in the sequence. These LLR values are also referred to as reliability information.
A processor implementing a MAP algorithm computes LLR values using α values (forward state probabilities for states in the trellis and also known as a forward recursion) and, β values (reverse state probabilities in the trellis and also known as a backward recursion), as described subsequently. The α values are associated with states within the trellis, and these α values are stored in memory. The processor using a MAP algorithm computes values of β, and the α values are then retrieved from memory to compute the final output LLR values.
The variable S is defined as the possible state (from a set of possible states {sp}p=0M−1) of the Markov process at time i, y, is defined as the noisy channel output sample at time i, the sample sequence yK is defined as the sequence of length K of noisy channel output samples
            {              y        i            }              i      =      0              K      -      1        ,and ylK is the noisy channel output sample yl at time i in a given sequence yK of length K. For a data block of length K, probability functions at time i may be defined for the Markov process as given in equations (1) through (3):
                              α          s          i                =                  p          (                                    S              =              s                        ;                          y              i              K                                )                                    (        1        )                                          β          s          i                =                  p          (                                                    y                                  i                  +                  1                                K                            |              S                        =            s                    )                                    (        2        )                                          γ                                    s              ′                        ,            s                    i                =                              p            (                                          S                =                s                            ;                                                                    y                    i                    K                                    |                                      S                    ′                                                  =                                  s                  ′                                                      )                    .                                    (        3        )            where S is the Markov process variable at time i, S′ is the Markov process variable at time i−1, s is the observed state of S of the Markov process at time i, and s′ is the observed state of S′ of the Markov process at time i−1.
The log-likelihood ratio (LLR) value L(ul) for a user's symbol ul at time i may then be calculated as given in equation (4):
                              L          ⁡                      (                          u              i                        )                          =                              log            ⁡                          (                                                p                  (                                                            u                      i                                        =                                                                  +                        1                                            |                                              y                        i                        K                                                                              )                                                  p                  (                                                            u                      i                                        =                                                                  -                        1                                            |                                              y                        i                        K                                                                              )                                            )                                .                                    (        4        )            
Defining αl1 and βl1 from equations (1) and (2) as the forward and backward recursions (probabilities or state metrics) at time i in state s=l, respectively, and defining
  γ      m    ,    l    ias the branch metric associated with the transition from state m at time i−1 to state l at time i, then the forward recursion for states is given in equation (5):
                                          α            l            i                    =                                    ∑                              l                ∈                S                                      ⁢                                          α                l                                  i                  -                  1                                            ⁢                              γ                                  m                  ,                  l                                i                                                    ,                            (        5        )            where lεS is a set of states at time i−1 which have a valid transition to the state l at time i.
Similarly, the backward recursion for states is given in equation (6):
                                          β            l                          i              -              1                                =                                    ∑                              m                ∈                S                                      ⁢                                          β                m                i                            ⁢                              γ                                  l                  ,                  m                                i                                                    ,                            (        6        )            where mεS is a set of states at time i which have a valid transition from the state l to the state m at time i−1.
Once the forward and backward recursions for states are calculated, equation (4) is employed to generate the log-likelihood value (also known as reliability value) L(ul) for each user symbol ul, Thus, equation (4) may be re-written as given in equation (7):
                              L          ⁡                      (                          u              i                        )                          =                  log          ⁡                      (                                                            ∑                                                            (                                              l                        ,                        m                                            )                                        ∈                                          S                      +                                                                      ⁢                                                      α                    l                                          i                      -                      1                                                        ⁢                                      γ                                          l                      ,                      m                                        i                                    ⁢                                      β                    l                    i                                                                                                ∑                                                            (                                              l                        ,                        m                                            )                                        ∈                                          S                      -                                                                      ⁢                                                      α                    l                                          i                      -                      1                                                        ⁢                                      γ                                          l                      ,                      m                                        i                                    ⁢                                      β                    m                    i                                                                        )                                              (        7        )            where a state pair (l, m)εS+ is defined as a pair that has a transition from state l at time i−1 to state m at time i corresponding to the user symbol ul=“1”, and a state pair (l, m)εS− is similarly defined as a pair that has a transition from state l at time i−1 to state m at time i corresponding to the user symbol ul=“−1”.
A MAP algorithm may be defined by substituting Am1=ln(αm1), Bm1=ln (βm1), and
      Γ          l      ,      m        i    =      ln    ⁡          (              γ                  l          ,          m                i            )      into the equations (5), (6), and (7). Such substitution is sometimes referred to as the log-MAP algorithm. Also, with the relation that ln(e−x+e−y) is equivalent to max(x,y)+ln(e−|−y|+1), the forward and backward recursions of the log MAP algorithm may be described as in equations (8) and (9):
                              A          m          i                =                              max                          l              ∈              S                                ⁢                      *                          (                                                A                  l                                      i                    -                    1                                                  +                                  Γ                                      l                    ,                    m                                    i                                            )                                                          (        8        )                                          B          l                      i            -            1                          =                              max                          m              ∈              S                                ⁢                      *                          (                                                B                  m                                      i                    -                    1                                                  +                                  Γ                                      l                    ,                    m                                    i                                            )                                                          (        9        )            where max* (x, y) is defined as max(x, y)+ln((e−|x−y|)+1). Note that equations (8) and (9) may include more than two terms in the max*( ) operator, so a max*(x, y, . . . , z) operation may be performed as a series of pairs of max*(•,•) calculations. Max(x, y) is defined as the “max term” and ln((e−|x−y|)+1) is defined as the “logarithmic correction term.”